package ai.zixing.mashibing.advance_class.secend.class02;

import java.util.Map;

/**
 * 给定一个正整数组成的无序数组arr，给定一个正整数值K
 * 找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的
 * 返回其长度
 *
 * 子数组、子串： 连续的
 * 子序列： 不连续
 */
public class Code01_LongestSumSubArrayLengthInPositiveArray {

    public static void main(String[] args) {
        int testTime = 100000;
        int size = 30;
        int value = 30;
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int[] array = generatorArray(size, value);
            int k = (int) (Math.random() * value) + 1;
            int ans1 = maxLength(array, k);
            int ans2 = right(array, k);
            if (ans2 != ans1) {
                System.out.println("error");
            }
        }
        System.out.println("test end");
    }

    // 窗口滑动
    private static int maxLength(int[] arr, int k) {
        if (arr == null || arr.length < 1 || k < 0) {
            return 0;
        }
        int max = 0;
        // L..R [L..R]
        int L = 0;
        int R = 0;
        int wSum = arr[0];
        while (R < arr.length) {
            if (wSum < k) {
                R++;
                // R++ 后可能越界，跳出
                if (R == arr.length) {
                    break;
                }
                wSum += arr[R];
            } else if (wSum > k) {
                wSum -= arr[L++];
            } else {
                max = Math.max(max, R - L + 1);
                wSum -= arr[L++];
            }
        }
        return max;
    }

    private static int right(int[] arr, int k) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (getSum(arr, i, j) == k) {
                    max = Math.max(max, j - i + 1);
                }
            }
        }
        return max;
    }

    private static int getSum(int[] arr, int L, int R) {
        int sum = 0;
        for (int k = L; k <= R; k++) {
            sum += arr[k];
        }
        return sum;
    }

    private static int[] generatorArray(int size, int value) {
        int[] arr = new int[(int) (Math.random() * size) + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * value) + 1;
        }
        return arr;
    }
}
